class Solution {
public:
    vector<string> letterCombinations(string digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> strs(10);
        strs[2] = "abc";
        strs[3] = "def";
        strs[4] = "ghi";
        strs[5] = "jkl";
        strs[6] = "mno";
        strs[7] = "pqrs";
        strs[8] = "tuv";
        strs[9] = "wxyz";
        string cur;
        vector<string> ans;
        calculate(0, digits, strs, cur, ans);
        return ans;
    }

    void calculate(int depth, const string &digits, const vector<string> &strs, string &cur, vector<string> &ans) {
        if (depth == digits.length()) {
            ans.push_back(cur);
            return;
        }
        string str = strs[digits[depth] - '0'];
        for (int i = 0; i < str.length(); ++i) {
            cur += str[i];
            calculate(depth + 1, digits, strs, cur, ans);
            cur.erase(cur.length() - 1, 1);
        }
    }

};
